/**
 * @brief 双链表的实现
 * @author TMJ
 * @date 2023-12-24
 * @version 1.0
 */

#ifndef LINEAR_TABLE_DOUBLE_LINK_LIST_H
#define LINEAR_TABLE_DOUBLE_LINK_LIST_H

#include <new>
#include <iostream>
#include "linear_list.h"

// 双链表的结点定义
template<typename type>
struct DoubleLinkNode {
    explicit DoubleLinkNode(DoubleLinkNode<type> *prev = nullptr, DoubleLinkNode<type> *next = nullptr) :
            prev(prev), next(next) {}

    explicit DoubleLinkNode(const type &data,
                            DoubleLinkNode<type> *prev = nullptr, DoubleLinkNode<type> *next = nullptr) :
            data(data), prev(prev), next(next) {}

    type data;                   // 数据
    DoubleLinkNode<type> *prev;  // 前驱指针
    DoubleLinkNode<type> *next;  // 后继指针
};

// 双链表的结构定义
template<typename type>
class DoubleLinkList
        : public LinearList<type> {
public:

    // 默认构造函数
    DoubleLinkList();

    // 析构函数
    ~DoubleLinkList();

    // 清空链表
    void clear();

    // 获取结点
    DoubleLinkNode<type> *getNode(int pos) const;

    // 搜索数据元素
    DoubleLinkNode<type> *search(const type &data) const;

    // 获取链表长度
    virtual int getLength() const;

    // 获取指定位置的元素的值
    virtual bool getData(int pos, type &data) const;

    // 设置指定位置的元素的值
    virtual bool setData(int pos, const type &data) const;

    // 在指定位置插入元素
    virtual bool insertData(int pos, const type &data);

    // 删除指定位置的元素
    virtual bool removeData(int pos, type &data);

    // 判断是否为空
    virtual bool isEmpty() const;

    // 打印
    virtual void print();

private:
    DoubleLinkNode<type> *_head;  // 头指针
    DoubleLinkNode<type> *_tail;  // 尾指针
    int _length;                  // 长度
};

// 默认构造函数
template<typename type>
DoubleLinkList<type>::DoubleLinkList() {
    this->_head = new DoubleLinkNode<type>();
    if (!this->_head) {
        throw std::bad_alloc();
    }

    this->_tail = new DoubleLinkNode<type>();
    if (!this->_tail) {
        throw std::bad_alloc();
    }

    this->_head->next = this->_tail;
    this->_tail->next = this->_head;

    this->_length = 0;
}

// 析构函数
template<typename type>
DoubleLinkList<type>::~DoubleLinkList() {
    this->clear();
    delete this->_tail;
    delete this->_head;
}

// 清空双链表
template<typename type>
void DoubleLinkList<type>::clear() {
    int length = this->_length;
    for (int i = 1; i <= length; i++) {
        type data;
        this->removeData(1, data);
    }
}

// 获取指定位置的结点
template<typename type>
DoubleLinkNode<type> *DoubleLinkList<type>::getNode(int pos) const {
    // 非法性检测
    if (pos <= 0 || pos > this->_length) {
        return nullptr;
    }

    DoubleLinkNode<type> *cur = this->_head;
    for (int i = 0; i <= pos; i++) {
        cur = cur->next;
    }

    return cur;
}

// 搜索结点
template<typename type>
DoubleLinkNode<type> *DoubleLinkList<type>::search(const type &data) const {
    for (DoubleLinkNode<type> *cur = this->_head; cur != nullptr; cur = cur->next) {
        if (cur->data == data) {
            return cur;
        }
    }

    return nullptr;
}

// 获取链表长度
template<typename type>
int DoubleLinkList<type>::getLength() const {
    return this->_length;
}

// 获取指定位置的值
template<typename type>
bool DoubleLinkList<type>::getData(int pos, type &data) const {
    if (pos <= 0 || pos > this->_length) {
        return false;
    }

    DoubleLinkNode<type> *cur = this->_head;
    for (int i = 0; i < pos; i++) {
        cur = cur->next;
    }
    data = cur->data;

    return true;
}

// 设置指定结点的元素值
template<typename type>
bool DoubleLinkList<type>::setData(int pos, const type &data) const {
    if (pos < 0 || pos > this->_length) {
        return false;
    }

    DoubleLinkNode<type> *cur = this->_head;
    for (int i = 0; i < pos; i++) {
        cur = cur->next;
    }
    cur->data = data;

    return true;
}

// 插入结点
template<typename type>
bool DoubleLinkList<type>::insertData(int pos, const type &data) {
    if (pos < 0 || pos > this->_length + 1) {
        return false;
    }

    DoubleLinkNode<type> *prev = this->_head;
    DoubleLinkNode<type> *cur = prev->next;
    int index = 1;

    while (index != pos) {
        prev = prev->next;
        cur = prev->next;
        index++;
    }

    auto *newNode = new DoubleLinkNode<type>(data, prev, cur);
    prev->next = newNode;
    cur->prev = newNode;

    this->_length++;

    return true;
}

// 删除指定元素
template<typename type>
bool DoubleLinkList<type>::removeData(int pos, type &data) {
    if (this->isEmpty() || pos < 0 || pos > this->_length) {
        return false;
    }

    DoubleLinkNode<type> *prev = this->_head;
    DoubleLinkNode<type> *cur = prev->next;
    int index = 1;

    while (index != pos) {
        prev = prev->next;
        cur = prev->next;
        index++;
    }

    cur->next->prev = prev;
    prev->next = cur->next;

    delete cur;
    this->_length--;

    return true;
}

template<typename type>
bool DoubleLinkList<type>::isEmpty() const {
    return this->_length == 0;
}

template<typename type>
void DoubleLinkList<type>::print() {
    if (this->_length == 0) {
        std::cout << "Empty list" << std::endl;
        return;
    }

    std::cout << "打印双向链表: { ";
    DoubleLinkNode<type> *cur = this->_head->next;
    for (int pos = 1; pos <= getLength(); pos++) {
        std::cout << cur->data;
        if (pos != getLength()) {
            std::cout << "<-->";
        }
        cur = cur->next;
    }
    std::cout << " }" << std::endl;
}


#endif //LINEAR_TABLE_DOUBLE_LINK_LIST_H
